This invention relates to pattern recognition and more particularly this invention relates to applications of mathematical techniques based on molecular genetics.
It has been observed that certain genetic processes can be described and analyzed mathematically, particularly by nonlinear mathematics. It has been observed that there are underlying similarities between digital information and molecular genetics. An example is the discovery that actual molecular biological reactions can be used to solve mathematical problems, such as the xe2x80x9ctraveling salesmanxe2x80x9d routing problem. (Dr. Leonard Adleman, a computer scientist at U.S.C., created an artificial DNA string for each node in a space and allowed the DNA strings to combine to define a singular path. L. Adleman, xe2x80x9cMolecular Computation of Solutions to Combinatorial Problems.xe2x80x9d Science Magazine. Vol. 266, Nov. 11, 1994.)
U.S. Patents and references were identified in an investigation of the prior art and are cited to the U.S. Patent Office in a separate Invention Disclosure Statement. Nothing showed the use of biomathematical techniques for texture or pattern recognition.
Of the references uncovered, U.S. Pat. No. 5,375,195 to Johnston shows the use of xe2x80x9cgenetic algorithmsxe2x80x9d to effect facial recognition, drawing on the techniques of mutation, phenotyping, gene, genotyping and crossover with mathematical processes. The use of the term xe2x80x9cgenetic algorithmxe2x80x9d therein and elsewhere in the literature refers to recombining and selecting functions which mimic the processes occurring in natural genetic reproduction in living organisms.
The only known precedent for the use of the term xe2x80x9cgenetic algorithmxe2x80x9d beyond the conventional use as in Johnston is in Adleman""s work in solution of the Hamiltonian path problem. The equivalent term for Adleman""s process is xe2x80x9cmolecular computation.xe2x80x9d Adleman""s work has spawned a new field of research investigation, which so far has lead to computational tools and elements, which is reported in the research science literature. An example is the proceedings of the Discrete Mathematics and Computer Science Workshop held Apr. 4, 1995 at Princeton University.
A 1981 Ph.D. dissertation entitled xe2x80x9cComputational Models for Texture Analysis and Texture Synthesisxe2x80x9d by David Garber at the University of Southern California discussed the concept of the use of N-gram statistics in texture analysis and generation. His analysis used a technique involving a maximum of N equal to four pixels in a row to determine fourth order statistical analysis to extract parameter sets in texture generation. He was able to correlate textures of different orders based on statistical analysis of pixel groupings. While never treated as image fragments, the present inventor has recognized a relationship between the concept of N-grams and the pixel groupings of contiguous pixels used in the present invention to create probes.
What is needed is an improved method to solve mathematically-challenging pattern problems, such as pattern recognition problems, including xe2x80x9cedgexe2x80x9d detection within a dataset (rather xe2x80x9cedgexe2x80x9d detection on a physical structure) wherein the dataset has an unarticulated but definable topology. The following invention exploits similarities between the genetic pattern recognition problems in the realm of image topology, where the topology is a function of relationships between pixels of an image.
According to the invention, in an analysis of a set of discrete multidimensional data which can be represented in an array with a topology, where the array that can be mapped to an image space of discrete elements, such as digitized image data, seismic data and audio data, genotype/phenotype classifications are imposed on the topology, and then molecular biological-like processes (annealing, fragmentation, chromatographic separation, fingerprinting, footprinting and filtering) are imposed upon that topology to perceive classifiable regions such as edges. More specifically, an image feature probe constructed of strings of contiguous image fragments of the class of N-grams called linear N-grams, anneals genotypes of topological features by complementary biological-like techniques in the same manner that complex biological systems are analyzed by genetic mapping, sequencing and cloning techniques. For example, molecular biological probes anneal with molecular biological genotypes and then are used to classify those genotypes. These topological genotypes are by definition orthogonal elements to edges.
The image fragments may be resolution independent. However, the image fragments can likewise be pixel strings where the pixels delimit the resolution of the image. Nevertheless, the probe derived from the image fragment can be constructed with an informational vector that is not limited by the resolution of the pixel representation. It is merely necessary that any informational vector, such as shape defined as a gradient in an analysis space, be compatible with the analysis space.
In the present invention, the process of applying genetic analysis techniques is analogized in the realm of digital computing, including the mimicking of functions carried out by molecular biologists in genetic analysis for biotechnology. Some of these techniques may be based on natural processes carried out by extra-chromosomal genetic elements. Some techniques have also been engineered by researchers. The genetic analysis techniques of the present invention are used for the image processing needed in pattern recognition and in particular texture recognition. Various methods for constructing probes are described.
The provisional application described a process involving a probe constructed from image fragment data to yield a type code. The present description further expounds on that description by recognizing that two types of information can be derived from a data array (such as pixel image data) to form a probe to yield a type code. The sequence that makes up a probe can be a sequence of entities (pixels) in an array and a sequence of differences between entities of the array.
The invention will be better understood upon reference to the following description in connection with the accompanying drawings.